package com.atwy.graph.directedgraph;

/**
 * @Author: 小王子火
 * @Date: 2022/3/19
 * 计算强连通分量
 *
 * 有向图中两个顶点v和w是相互可达的，则称它们是强连通的。
 * 如果一幅有向图中的任意两个顶点都是强连通的，则称该有向图也是强连通的。
 *
 * 两个顶点是强连通的，当且仅当它们都在一个普通的有向环中。
 *
 * 作为一种等价关系，强连通性将所有顶点分为了一些等价类，
 * 每个等价类都是相互均为强连通的顶点的最大子集组成。这些子集称为强连通分量。
 *
 * 注意：强连通分量的定义是基于顶点，而非边。
 *
 * Kosaraju算法：与无向图的ConnectedComponent计算连通分量差不多，只是多了一些处理
 * 1、在给定的一幅有向图G中，使用DepthFirstOrder来计算它的反向图GR的逆后序排列。
 * 2、在G中进行标准的深度优先搜索，但是按照刚才计算得来的顺序而非标准的顺序来访问所有未被标记的顶点。
 * 3、在构造函数中，所有在同一个递归dfs()调用中被访问到的顶点都在同一个强连通分量中，
 * 将它们按照和CC相同的方式识别出来。
 */
public class KosarajuCC {
    /**
     * 记录某个顶点是否被访问到
     */
    private boolean[] marked;
    /**
     * 强连通分量的标识符
     */
    private int[] id;
    /**
     * 强连通分量的数量
     */
    private int count;

    public KosarajuCC(IDigraph graph) {
        marked = new boolean[graph.V()];
        id = new int[graph.V()];
        // 反向图的逆后序排列
        DepthFirstOrder order = new DepthFirstOrder(graph.reverse());
        for (int s : order.reversePost()){
            if (!marked[s]){
                dfs(graph,s);
                // 所有和s连通的顶点都在上面dfs递归栈中被访问到
                count++;
            }
        }

    }

    private void dfs(IDigraph graph, int v) {
        id[v] = count;
        marked[v] = true;
        for (int w : graph.adj(v)){
            if(!marked[w]){
                dfs(graph,w);
            }
        }
    }

    public boolean stronglyConnected(int v,int w){
        return id[v] == id[w];
    }

    public int id(int v){
        return id[v];
    }

    public int count(){
        return count;
    }
}
